package com.leetcodehot.problems;

import java.util.Arrays;

public class problems2187 {
    /**
     * 给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
     * <p>
     * 每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
     * <p>
     * 给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
     */
    public boolean isOk(int total, int[] time, long mid) {
        //用mid公共时间 能否跑完total次
        if (time.length == 1) {
            return (long) time[0] * (long) total <= mid;
        }
        double count = 0;
        for (int i = 0; i < time.length; i++) {
            count += mid / time[i];
            if (count >= total) return true;
        }
        return count >= total;
    }

    public long minimumTime(int[] time, int totalTrips) {
        int n = time.length;
        Arrays.sort(time);
        int minT = Integer.MAX_VALUE;
        int maxT = 0;
        for (int t : time) {
            minT = Math.min(minT, t);
            maxT = Math.max(maxT, t);
        }
        int avg = (totalTrips - 1) / time.length + 1;
        long left = (long) minT * avg - 1;
        long right = (long) maxT * avg;
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (isOk(totalTrips, time, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
